package day4;

import java.util.ArrayList;

public class Main3 {
    /**
     * NC393 取金币
     * https://www.nowcoder.com/practice/cb33f5653a064b2eaf1fe30ba18f5977?tpId=196&tqId=40524&ru=/exam/oj
     */
    public int getCoins (ArrayList<Integer> coins) {
        int n = coins.size();
        int[] arr= new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for(int i = 1;i <= n;i++) {
            arr[i] = coins.get(i - 1);
        }
        // dp[i][j]: 表示区间[i,j]的金币全部拿走，得到的最大积分是多少
        int[][] dp = new int[n + 2][n + 2];
        // 从下往上，从左往右
        for(int i = n;i >= 1;i--) {
            for(int j = i;j <= n;j++) {
                for(int k = i;k <= j;k++) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);
                }
            }
        }
        return dp[1][n];
    }
}
